package algorithm.poj.p2000;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.math.BigInteger;
import java.net.URL;
import java.net.URLDecoder;


/**
 * 分析：
 * 
 * A(0) = 1
 * A(1) = 01
 * A(2) = 1001
 * A(3) = 01101001
 * ...
 * 仔细观察可以知道，A(n+1)实际上是A(n)的反数与A(n)拼接在一起： A(n+1) = ~A(n)A(n)
 * 设A(n)中00, 01, 10, 11的个数分别是x(n), y(n), z(n), t(n)个，那么有：
 * x(n+1) = x(n) + t(n) + [2|(n-1)]
 * y(n+1) = y(n) + z(n) + [2|n]
 * z(n+1) = z(n) + y(n)
 * t(n+1) = x(n) + t(n)
 * 其中:		
 * 	x(1) = 0, y(1) = 1, z(1) = 0, t(1) = 0,
 * 	x(2) = 1, y(2) = 1, z(2) = 1, t(2) = 0,
 *  x(3) = 1, y(3) = 3, z(3) = 2, t(3) = 1,
 *  x(4) = 3, ...
 *  
 * 我们只要求解x(n)就行。
 * 
 *    x(n+1) = t(n+1) + [2|(n-1)]
 * => x(n) = t(n) + [2|n]
 * => x(n+1) = 2*x[n] - [2|n] + [2|(n-1)]
 * => x(2k+1) = 4*x(2k-1) + 1
 *    x(2k+2) = 4*x(2k) - 1 
 * => x(2k+1) = (2^(2k) - 1)/3
 *    x(2k+2) = (2^(2k+1) + 1)/3
 *    
 * 实现：
 * 
 * 经验：
 * 
 * 教训：
 * 
 * @author wong.tong@gmail.com
 *
 */
public class P2680 {

	public static void main(String[] args) throws Exception {

		InputStream input = null;
		if (false) {
			input = System.in;
		} else {
			URL url = P2680.class.getResource("P2680.txt");
			File file = new File(URLDecoder.decode(url.getPath(), "UTF-8"));
			input = new FileInputStream(file);
		}
		
		BufferedReader stdin = new BufferedReader(new InputStreamReader(input));
		
		BigInteger[] m = init(1000);
		String line = stdin.readLine();
		while (line != null) {
			int n = Integer.valueOf(line);
			System.out.println(m[n-1].toString());
			line = stdin.readLine();
		}
	}
	
	
	private static BigInteger[] init(int n) {
		
		BigInteger[] m = new BigInteger[n];
		m[0] = BigInteger.ZERO;
		m[1] = BigInteger.ONE;
		BigInteger n4 = BigInteger.valueOf(4);
		for (int i = 2; i < n; i ++) {
			if (i%2 == 0) {
				m[i] = m[i-2].multiply(n4).add(BigInteger.ONE);
			} else {
				m[i] = m[i-2].multiply(n4).subtract(BigInteger.ONE);
			}
		}
		return m;
	}
}
